-tape Turing machine

$ k-tape (deterministic) Turing machine, $ k-tape TM

#計算モデル

#チューリングマシン

1本の入力テープ（読み込み可能・書き込み不能）と$ k-2本の作業テープ（読み込み可能・書き込み可能）, 1本の出力テープ（読み込み可能・書き込み可能）からなるTM

Computational Complexity: A Modern Approachでは標準的なチューリングマシンとして扱われている

記法

空列を$ \braket{}と書く

記号列を$ \braket{x_1,x_2,...}と書く

記号列の$ i番目の記号を$ (\sigma)_iと書く

記号列$ \sigma, \tau のの結合を$ \sigma^\frown \tauと書く

記号$ xの$ \kappa反復を$ x^\kappaと書く

$ x^\kappa \coloneqq \braket{\underbrace{x,..., x}_\kappa}

記号列$ \sigma の$ i 文字目を$ x に書き換える操作を$ \sigma[i \mapsto x] と書く

$ \braket{(\sigma)_0, ..., (\sigma)_{i-1}, (\sigma)_i, (\sigma)_{i+1}, ...}[i \mapsto x] = \braket{(\sigma)_0, ..., (\sigma)_{i-1}, x, (\sigma)_{i+1}, ...}

定義

$ k \ge 2

$ k-tape Turing machine$ Mは以下の3組である

$ M = (\Gamma, Q,\delta)

$ \Gamma: \text{finite set}

空白記号, 開始記号, $ 0, 1を含む

$ \Box, \triangleright, 0, 1 \in \Gamma

テープ上の記号を意味する

$ Q:\text{finite set}

開始記号, 終了記号を含む

$ q_\mathsf{start}, q_\mathsf{halt} \in Q

内部状態を意味する

$ \delta\colon Q \times \Gamma^k \to Q \times \Gamma^{k-1} \times \{\mathsf{L, S,R}\}^k

ステップごとの内部状態$ Qの更新, $ k-1本の作業テープのヘッド上の文字$ \Gammaの更新, $ k本のテープのヘッドの移動の命令$ \sf L{\scriptsize eft}, S{\scriptsize tay}, R{\scriptsize ight}を決定する関数

$ Q, \Gamma共に有限集合なので$ \deltaも有限集合で表現可能

$ k-tape Turing machine$ Mは三種類のテープを持つ

$ T_0：入力テープ

$ T_1, ..., T_{k-2}：作業テープ

$ T_{k-1}：出力テープ

定義：計算

$ M = (\Gamma, Q, \delta)

入力列を$ x \in 2^*とする

以下のようにステップ$ s \in \Nのときの

テープの状態$ T_0^s, ..., T_{k-1}^s \in \Gamma^\omega

ヘッドの位置 $ h_0^s, ..., h_{k-1}^s \in \N

内部状態$ q^s \in Q

を定義する

初期状態

$ T^0_0 \coloneqq \braket{\triangleright}^\frown x^\frown \Box^\omega

$ T_{k+1}^0 \coloneqq \braket{\triangleright}^\frown\Box^\omega

$ h_k^0 \coloneqq 0

$ q^0 \coloneqq q_\mathsf{start}

計算

$ \delta(q^s, (T_0^s)_{h_0^s}, ..., (T_{k-1}^s)_{h_{k-1}^s}) = (q', y_1,...,y_{k-1}, j_0,...j_{k-1}) のとき

$ T_0^{s+1} \coloneqq T_0^s

$ T_{k+1}^{s+1} \coloneqq T_{k+1}^s[h_{k+1}^s \mapsto y_{k+1}]

$ h_k^{s+1} \coloneqq \begin{cases} h_k^s - 1 & \text{if $j_k = \mathsf{L}$} \\ h_k^s & \text{if $j_k = \mathsf{S}$} \\ h_k^s + 1 & \text{if $j_k = \mathsf{R}$} \end{cases}

$ q^{s+1} \coloneqq q'

$ s \ge \min\{s | q^s = q_\mathsf{halt}\}であるような$ sが存在するとき$ M(x)は$ sで停止したといい

$ M_s(x)\downarrow

とかく

$ M(x)が$ sで停止し, $ y \in 2^*が存在して$ T_{k-1}^s = \braket{\triangleright}^\frown y^\frown\Box^\omegaであるとき, $ M(x)の出力は$ yであり

$ M_s(x) =_\downarrow y

とかく

$ M_s(x) =_\downarrow y かつ$ l \ge \max\{h_0^u, ..., h_{k-1}^u\ |\ u < s\}のとき

$ M_{s,l}(x) =_\downarrow y

とかく

#Computational_Complexity:_A_Modern_Approach